﻿
namespace Leetcode.N0042;

public class Solution
{
    public int Trap(int[] heights)
    {
        var s = new System.Collections.Generic.Stack<int>();
        var area = 0;
        var cutHeights = new int[heights.Length];

        for (var i = 0; i < heights.Length; i++)
        {
            var curHeight = heights[i];
            while (s.Count > 0 && heights[s.Peek()] <= curHeight)
            {
                var popIndex = s.Pop();
                area += (i - popIndex - 1) * (heights[popIndex] - cutHeights[popIndex]);
            }

            if (s.Count > 0)
            {
                var preIndex = s.Peek();
                area += (i - preIndex - 1) * (curHeight - cutHeights[preIndex]);
                cutHeights[preIndex] = curHeight;
            }

            s.Push(i);
        }

        return area;
    }
}
